# 给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
#
#  示例 1:
#
#  输入: "aacecaaa"
# 输出: "aaacecaaa"
#
#
#  示例 2:
#
#  输入: "abcd"
# 输出: "dcbabcd"
#  Related Topics 字符串
#  👍 260 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def shortestPalindrome(self, s: str) -> str:

        if len(s) == 1:
            return s

        r = [0] * 4

        for i in range(0, len(s)):
            left = i - 1
            right = i + 1

            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1

            if right - left + 1 > r[1] - r[0]:
                r[0], r[1] = left, right

            left1 = i
            right1 = i + 1

            while left1 >= 0 and right1 < len(s) and s[left1] == s[right1]:
                left1 -= 1
                right1 += 1

            if right1 - left1 + 1 > r[3] - r[2]:
                r[3], r[2] = left1, right1

        start, end = (r[0] + 1, r[1]) if r[1] - r[0] > r[3] - r[2] else (r[2] + 1, r[3])

        # 只能在字符串前面添加字符
        if start == 0:
            return s[end:] + s
        else:
            return s[::-1][:len(s)-1] + s

    # leetcode submit region end(Prohibit modification and deletion)


print(Solution().shortestPalindrome("abcd"))
